home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 1999 August / SGI Freeware 1999 August.iso / dist / samba.idb / usr / samba / src / source / ubiqx / ubi_Cache.h.z / ubi_Cache.h
Encoding:
C/C++ Source or Header  |  1998-10-28  |  18.3 KB  |  399 lines
  1. #ifndef UBI_CACHE_H
  2. #define UBI_CACHE_H
  3. /* ========================================================================== **
  4.  *                                 ubi_Cache.h
  5.  *
  6.  *  Copyright (C) 1997 by Christopher R. Hertel
  7.  *
  8.  *  Email: crh@ubiqx.mn.org
  9.  * -------------------------------------------------------------------------- **
  10.  *
  11.  *  This module implements a generic cache.
  12.  *
  13.  * -------------------------------------------------------------------------- **
  14.  *
  15.  *  This library is free software; you can redistribute it and/or
  16.  *  modify it under the terms of the GNU Library General Public
  17.  *  License as published by the Free Software Foundation; either
  18.  *  version 2 of the License, or (at your option) any later version.
  19.  *
  20.  *  This library is distributed in the hope that it will be useful,
  21.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  22.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  23.  *  Library General Public License for more details.
  24.  *
  25.  *  You should have received a copy of the GNU Library General Public
  26.  *  License along with this library; if not, write to the Free
  27.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  28.  *
  29.  * -------------------------------------------------------------------------- **
  30.  *
  31.  *  This module uses a splay tree to implement a simple cache.  The cache
  32.  *  module adds a thin layer of functionality to the splay tree.  In
  33.  *  particular:
  34.  *
  35.  *    - The tree (cache) may be limited in size by the number of
  36.  *      entries permitted or the amount of memory used.  When either
  37.  *      limit is exceeded cache entries are removed until the cache
  38.  *      conforms.
  39.  *    - Some statistical information is kept so that an approximate
  40.  *      "hit ratio" can be calculated.
  41.  *    - There are several functions available that provide access to
  42.  *      and management of cache size limits, hit ratio, and tree
  43.  *      trimming.
  44.  *
  45.  *  The splay tree is used because recently accessed items tend toward the
  46.  *  top of the tree and less recently accessed items tend toward the bottom.
  47.  *  This makes it easy to purge less recently used items should the cache
  48.  *  exceed its limits.
  49.  *
  50.  *  To use this module, you will need to supply a comparison function of
  51.  *  type ubi_trCompFunc and a node-freeing function of type
  52.  *  ubi_trKillNodeTrn.  See ubi_BinTree.h for more information on
  53.  *  these.  (This is all basic ubiqx tree management stuff.)
  54.  *
  55.  *  Notes:
  56.  *
  57.  *  - Cache performance will start to suffer dramatically if the
  58.  *    cache becomes large enough to force the OS to start swapping
  59.  *    memory to disk.  This is because the nodes of the underlying tree
  60.  *    will be scattered across memory in an order that is completely
  61.  *    unrelated to their traversal order.  As more and more of the
  62.  *    cache is placed into swap space, more and more swaps will be
  63.  *    required for a simple traversal (...and then there's the splay
  64.  *    operation).
  65.  *
  66.  *    In one simple test under Linux, the load and dump of a cache of
  67.  *    400,000 entries took only 1min, 40sec of real time.  The same
  68.  *    test with 450,000 records took 2 *hours* and eight minutes.
  69.  *
  70.  *  - In an effort to save memory, I considered using an unsigned
  71.  *    short to save the per-entry entry size.  I would have tucked this
  72.  *    value into some unused space in the tree node structure.  On
  73.  *    32-bit word aligned systems this would have saved an additional
  74.  *    four bytes per entry.  I may revisit this issue, but for now I've
  75.  *    decided against it.
  76.  *
  77.  *    Using an unsigned short would limit the size of an entry to 64K
  78.  *    bytes.  That's probably more than enough for most applications.
  79.  *    The key word in that last sentence, however, is "probably".  I
  80.  *    really dislike imposing such limits on things.
  81.  *
  82.  *  - Each entry keeps track of the amount of memory it used and the
  83.  *    cache header keeps the total.  This information is provided via
  84.  *    the EntrySize parameter in ubi_cachePut(), so it is up to you to
  85.  *    make sure that the numbers are accurate.  (The numbers don't even
  86.  *    have to represent bytes used.)
  87.  *
  88.  *    As you consider this, note that the strdup() function--as an
  89.  *    example--will call malloc().  The latter generally allocates a
  90.  *    multiple of the system word size, which may be more than the
  91.  *    number of bytes needed to store the string.
  92.  *
  93.  * -------------------------------------------------------------------------- **
  94.  *
  95.  *  Log: ubi_Cache.h,v
  96.  *  Revision 0.0  1997/12/18 06:25:23  crh
  97.  *  Initial Revision.
  98.  *
  99.  * ========================================================================== **
  100.  */
  101.  
  102. #include "ubi_SplayTree.h"
  103.  
  104. /* -------------------------------------------------------------------------- **
  105.  * Typedefs...
  106.  *
  107.  *  ubi_cacheRoot     - Cache header structure, which consists of a binary
  108.  *                      tree root and other required housekeeping fields, as
  109.  *                      listed below.
  110.  *  ubi_cacheRootPtr  - Pointer to a Cache.
  111.  *
  112.  *  ubi_cacheEntry    - A cache Entry, which consists of a tree node
  113.  *                      structure and the size (in bytes) of the entry
  114.  *                      data.  The entry size should be supplied via
  115.  *                      the EntrySize parameter of the ubi_cachePut()
  116.  *                      function.
  117.  *
  118.  *  ubi_cacheEntryPtr - Pointer to a ubi_cacheEntry.
  119.  *
  120.  */
  121.  
  122. typedef struct
  123.   {
  124.   ubi_trRoot        root;         /* Splay tree control structure.      */
  125.   ubi_trKillNodeRtn free_func;    /* Function used to free entries.     */
  126.   unsigned long     max_entries;  /* Max cache entries.  0 == unlimited */
  127.   unsigned long     max_memory;   /* Max memory to use.  0 == unlimited */
  128.   unsigned long     mem_used;     /* Memory currently in use (bytes).   */
  129.   unsigned short    cache_hits;   /* Incremented on succesful find.     */
  130.   unsigned short    cache_trys;   /* Incremented on cache lookup.       */
  131.   } ubi_cacheRoot;
  132.  
  133. typedef ubi_cacheRoot *ubi_cacheRootPtr;
  134.  
  135.  
  136. typedef struct
  137.   {
  138.   ubi_trNode    node;           /* Tree node structure. */
  139.   unsigned long entry_size;     /* Entry size.  Used when managing
  140.                                  * caches with maximum memory limits.
  141.                                  */
  142.   } ubi_cacheEntry;
  143.  
  144. typedef ubi_cacheEntry *ubi_cacheEntryPtr;
  145.  
  146.  
  147. /* -------------------------------------------------------------------------- **
  148.  * Macros...
  149.  *
  150.  *  ubi_cacheGetMaxEntries()  - Report the current maximum number of entries
  151.  *                              allowed in the cache.  Zero indicates no
  152.  *                              maximum.
  153.  *  ubi_cacheGetMaxMemory()   - Report the current maximum amount of memory
  154.  *                              that may be used in the cache.  Zero
  155.  *                              indicates no maximum.
  156.  *  ubi_cacheGetEntryCount()  - Report the current number of entries in the
  157.  *                              cache.
  158.  *  ubi_cacheGetMemUsed()     - Report the amount of memory currently in use
  159.  *                              by the cache.
  160.  */
  161.  
  162. #define ubi_cacheGetMaxEntries( Cptr ) (((ubi_cacheRootPtr)(Cptr))->max_entries)
  163. #define ubi_cacheGetMaxMemory(  Cptr ) (((ubi_cacheRootPtr)(Cptr))->max_memory)
  164.  
  165. #define ubi_cacheGetEntryCount( Cptr ) (((ubi_cacheRootPtr)(Cptr))->root.count)
  166. #define ubi_cacheGetMemUsed( Cptr ) (((ubi_cacheRootPtr)(Cptr))->mem_used)
  167.  
  168. /* -------------------------------------------------------------------------- **
  169.  * Prototypes...
  170.  */
  171.  
  172. ubi_cacheRootPtr ubi_cacheInit( ubi_cacheRootPtr  CachePtr,
  173.                                 ubi_trCompFunc    CompFunc,
  174.                                 ubi_trKillNodeRtn FreeFunc,
  175.                                 unsigned long     MaxEntries,
  176.                                 unsigned long     MaxMemory );
  177.   /* ------------------------------------------------------------------------ **
  178.    * Initialize a cache header structure.
  179.    *
  180.    *  Input:  CachePtr    - A pointer to a ubi_cacheRoot structure that is
  181.    *                        to be initialized.
  182.    *          CompFunc    - A pointer to the function that will be called
  183.    *                        to compare two cache values.  See the module
  184.    *                        comments, above, for more information.
  185.    *          FreeFunc    - A pointer to a function that will be called
  186.    *                        to free a cache entry.  If you allocated
  187.    *                        the cache entry using malloc(), then this
  188.    *                        will likely be free().  If you are allocating
  189.    *                        cache entries from a free list, then this will
  190.    *                        likely be a function that returns memory to the
  191.    *                        free list, etc.
  192.    *          MaxEntries  - The maximum number of entries that will be
  193.    *                        allowed to exist in the cache.  If this limit
  194.    *                        is exceeded, then existing entries will be
  195.    *                        removed from the cache.  A value of zero
  196.    *                        indicates that there is no limit on the number
  197.    *                        of cache entries.  See ubi_cachePut().
  198.    *          MaxMemory   - The maximum amount of memory, in bytes, to be
  199.    *                        allocated to the cache (excluding the cache
  200.    *                        header).  If this is exceeded, existing entries
  201.    *                        in the cache will be removed until enough memory
  202.    *                        has been freed to meet the condition.  See
  203.    *                        ubi_cachePut().
  204.    *
  205.    *  Output: A pointer to the initialized cache (i.e., the same as CachePtr).
  206.    *
  207.    *  Notes:  Both MaxEntries and MaxMemory may be changed after the cache
  208.    *          has been created.  See
  209.    *            ubi_cacheSetMaxEntries() 
  210.    *            ubi_cacheSetMaxMemory()
  211.    *            ubi_cacheGetMaxEntries()
  212.    *            ubi_cacheGetMaxMemory()    (the latter two are macros).
  213.    *
  214.    *        - Memory is allocated in multiples of the word size.  The
  215.    *          return value of the strlen() function does not reflect
  216.    *          this; it will allways be less than or equal to the amount
  217.    *          of memory actually allocated.  Keep this in mind when
  218.    *          choosing a value for MaxMemory.
  219.    *
  220.    * ------------------------------------------------------------------------ **
  221.    */
  222.  
  223. ubi_cacheRootPtr ubi_cacheClear( ubi_cacheRootPtr CachePtr );
  224.   /* ------------------------------------------------------------------------ **
  225.    * Remove and free all entries in an existing cache.
  226.    *
  227.    *  Input:  CachePtr  - A pointer to the cache that is to be cleared.
  228.    *
  229.    *  Output: A pointer to the cache header (i.e., the same as CachePtr).
  230.    *          This function re-initializes the cache header.
  231.    *
  232.    * ------------------------------------------------------------------------ **
  233.    */
  234.  
  235. void ubi_cachePut( ubi_cacheRootPtr  CachePtr,
  236.                    unsigned long     EntrySize,
  237.                    ubi_cacheEntryPtr EntryPtr,
  238.                    ubi_trItemPtr     Key );
  239.   /* ------------------------------------------------------------------------ **
  240.    * Add an entry to the cache.
  241.    *
  242.    *  Input:  CachePtr  - A pointer to the cache into which the entry
  243.    *                      will be added.
  244.    *          EntrySize - The size, in bytes, of the memory block indicated
  245.    *                      by EntryPtr.  This will be copied into the
  246.    *                      EntryPtr->entry_size field.
  247.    *          EntryPtr  - A pointer to a memory block that begins with a
  248.    *                      ubi_cacheEntry structure.  The entry structure
  249.    *                      should be followed immediately by the data to be
  250.    *                      cached (even if that is a pointer to yet more data).
  251.    *          Key       - Pointer used to identify the lookup key within the
  252.    *                      Entry.
  253.    *
  254.    *  Output: None.
  255.    *
  256.    *  Notes:  After adding the new node, the cache is "trimmed".  This
  257.    *          removes extra nodes if the tree has exceeded it's memory or
  258.    *          entry count limits.  It is unlikely that the newly added node
  259.    *          will be purged from the cache (assuming a reasonably large
  260.    *          cache), since new nodes in a splay tree (which is what this
  261.    *          module was designed to use) are moved to the top of the tree
  262.    *          and the cache purge process removes nodes from the bottom of
  263.    *          the tree.
  264.    *        - The underlying splay tree is opened in OVERWRITE mode.  If
  265.    *          the input key matches an existing key, the existing entry will
  266.    *          be politely removed from the tree and freed.
  267.    *        - Memory is allocated in multiples of the word size.  The
  268.    *          return value of the strlen() function does not reflect
  269.    *          this; it will allways be less than or equal to the amount
  270.    *          of memory actually allocated.
  271.    *
  272.    * ------------------------------------------------------------------------ **
  273.    */
  274.  
  275. ubi_cacheEntryPtr ubi_cacheGet( ubi_cacheRootPtr CachePtr,
  276.                                 ubi_trItemPtr    FindMe );
  277.   /* ------------------------------------------------------------------------ **
  278.    * Attempt to retrieve an entry from the cache.
  279.    *
  280.    *  Input:  CachePtr  - A ponter to the cache that is to be searched.
  281.    *          FindMe    - A ubi_trItemPtr that indicates the key for which
  282.    *                      to search.
  283.    *
  284.    *  Output: A pointer to the cache entry that was found, or NULL if no
  285.    *          matching entry was found.
  286.    *
  287.    *  Notes:  This function also updates the hit ratio counters.
  288.    *          The counters are unsigned short.  If the number of cache tries
  289.    *          reaches 32768, then both the number of tries and the number of
  290.    *          hits are divided by two.  This prevents the counters from
  291.    *          overflowing.  See the comments in ubi_cacheHitRatio() for
  292.    *          additional notes.
  293.    *
  294.    * ------------------------------------------------------------------------ **
  295.    */
  296.  
  297. ubi_trBool ubi_cacheDelete( ubi_cacheRootPtr CachePtr, ubi_trItemPtr DeleteMe );
  298.   /* ------------------------------------------------------------------------ **
  299.    * Find and delete the specified cache entry.
  300.    *
  301.    *  Input:  CachePtr  - A pointer to the cache.
  302.    *          DeleteMe  - The key of the entry to be deleted.
  303.    *
  304.    *  Output: TRUE if the entry was found & freed, else FALSE.
  305.    *
  306.    * ------------------------------------------------------------------------ **
  307.    */
  308.  
  309. ubi_trBool ubi_cacheReduce( ubi_cacheRootPtr CachePtr, unsigned long count );
  310.   /* ------------------------------------------------------------------------ **
  311.    * Remove <count> entries from the bottom of the cache.
  312.    *
  313.    *  Input:  CachePtr  - A pointer to the cache which is to be reduced in
  314.    *                      size.
  315.    *          count     - The number of entries to remove.
  316.    *
  317.    *  Output: The function will return TRUE if <count> entries were removed,
  318.    *          else FALSE.  A return value of FALSE should indicate that
  319.    *          there were less than <count> entries in the cache, and that the
  320.    *          cache is now empty.
  321.    *
  322.    *  Notes:  This function forces a reduction in the number of cache entries
  323.    *          without requiring that the MaxMemory or MaxEntries values be
  324.    *          changed.
  325.    *
  326.    * ------------------------------------------------------------------------ **
  327.    */
  328.  
  329. unsigned long ubi_cacheSetMaxEntries( ubi_cacheRootPtr CachePtr,
  330.                                       unsigned long    NewSize );
  331.   /* ------------------------------------------------------------------------ **
  332.    * Change the maximum number of entries allowed to exist in the cache.
  333.    *
  334.    *  Input:  CachePtr  - A pointer to the cache to be modified.
  335.    *          NewSize   - The new maximum number of cache entries.
  336.    *
  337.    *  Output: The maximum number of entries previously allowed to exist in
  338.    *          the cache.
  339.    *
  340.    *  Notes:  If the new size is less than the old size, this function will
  341.    *          trim the cache (remove excess entries).
  342.    *        - A value of zero indicates an unlimited number of entries.
  343.    *
  344.    * ------------------------------------------------------------------------ **
  345.    */
  346.  
  347. unsigned long ubi_cacheSetMaxMemory( ubi_cacheRootPtr CachePtr,
  348.                                      unsigned long    NewSize );
  349.   /* ------------------------------------------------------------------------ **
  350.    * Change the maximum amount of memory to be used for storing cache
  351.    * entries.
  352.    *
  353.    *  Input:  CachePtr  - A pointer to the cache to be modified.
  354.    *          NewSize   - The new cache memory size.
  355.    *
  356.    *  Output: The previous maximum memory size.
  357.    *
  358.    *  Notes:  If the new size is less than the old size, this function will
  359.    *          trim the cache (remove excess entries).
  360.    *        - A value of zero indicates that the cache has no memory limit.
  361.    *
  362.    * ------------------------------------------------------------------------ **
  363.    */
  364.  
  365. int ubi_cacheHitRatio( ubi_cacheRootPtr CachePtr );
  366.   /* ------------------------------------------------------------------------ **
  367.    * Returns a value that is 10,000 times the slightly weighted average hit
  368.    * ratio for the cache.
  369.    *
  370.    *  Input:  CachePtr  - Pointer to the cache to be queried.
  371.    *
  372.    *  Output: An integer that is 10,000 times the number of successful
  373.    *          cache hits divided by the number of cache lookups, or:
  374.    *            (10000 * hits) / trys
  375.    *          You can easily convert this to a float, or do something
  376.    *          like this (where i is the return value of this function):
  377.    *
  378.    *            printf( "Hit rate   : %d.%02d%%\n", (i/100), (i%100) );
  379.    *
  380.    *  Notes:  I say "slightly-weighted", because the numerator and
  381.    *          denominator are both accumulated in locations of type
  382.    *          'unsigned short'.  If the number of cache trys becomes
  383.    *          large enough, both are divided  by two.  (See function
  384.    *          ubi_cacheGet().) 
  385.    *          Dividing both numerator and denominator by two does not
  386.    *          change the ratio (much...it is an integer divide), but it
  387.    *          does mean that subsequent increments to either counter will
  388.    *          have twice as much significance as previous ones. 
  389.    *
  390.    *        - The value returned by this function will be in the range
  391.    *          [0..10000] because ( 0 <= cache_hits <= cache_trys ) will
  392.    *          always be true.
  393.    *
  394.    * ------------------------------------------------------------------------ **
  395.    */
  396.  
  397. /* -------------------------------------------------------------------------- */
  398. #endif /* ubi_CACHE_H */
  399.